package com.example.system.class22;

/**
 * @Date 2022/8/23
 * @Author Jonathan
 * @Description 醉汉问题 走出去了就剪枝
 * </p>
 * 给定5个参数，N，M，row，col，k
 * 表示在N*M的区域上，醉汉Bob初始在(row,col)位置
 * Bob一共要迈出k步，且每步都会等概率向上下左右四个方向走一个单位
 * 任何时候Bob只要离开N*M的区域，就直接死亡
 * 返回k步之后，Bob还在N*M的区域的概率
 */
public class Code05_BobDie {
    public static void main(String[] args) {
        System.out.printf("存活概率:%f\n", livePossibility(3, 3, 2, 2, 1));
    }


    /**
     * 计算概率
     */
    public static double livePossibility(int M, int N, int row, int col, int k) {
        if (row < 0 || col < 0 || row >= M || col >= N) {
            return 0;
        }
        return process(M, N, row, col, k) / Math.pow(4, k);
    }

    private static int process(int M, int N, int row, int col, int rest) {
        if (rest == 0) {
            // 步数走完了之后  坐标是否还在格子之内
            return (row >= 0 && row < M && col >= 0 && col < N) ? 1 : 0;
        }
        int ans = 0;
        ans += process(M, N, row - 1, col, rest - 1);
        ans += process(M, N, row + 1, col, rest - 1);
        ans += process(M, N, row, col - 1, rest - 1);
        ans += process(M, N, row, col + 1, rest - 1);
        return ans;
    }


}
